As communication technology continues to advance, applications for the electronic communication of data continue to increase. However, the need for reliable data communication is also increasing. In certain communication applications, data is often exposed to interference, increasing the likelihood of communication errors. For example, data transmitted by way of a wireless communication network is often exposed to various forms of channel noise on the communication channel which may affect the data. Alternatively, obstacles such as buildings or natural obstructions may impede the path of data transmission, leading to burst errors which may affect larger blocks of data. Accordingly, error correction techniques are used to ensure that any errors in the transmission of data are reduced to an acceptable level for a given application.
Forward error correction (FEC) is a system of error control for data transmission often used in telecommunications applications. Convolutional coding is a type of FEC code in which each m-bit information symbol to be encoded is transformed into an n-bit symbol, where n is greater than or equal to m and m/n is the code rate. An example of a simple convolutional coding circuit is shown in FIG. 1. In particular, an input data A is input to a transform function Z0 to generate a value B. A second transform function Z1 receives the value B to generate a value C. A and C are added to generate an output 0, while A, B and C are added to generate an output 1. Accordingly, the circuit of FIG. 1 provides a half rate code where two bits are output for each input bit.
Data encoded using convolutional encoding is generally decoded with a trellis decoder, such as a Viterbi decoder. A trellis decoder operates by constructing a trellis of state probabilities and branch metrics. The transmitted data is often terminated with a number of zeros to force the encoder back to the zero state, allowing the decoder to start decoding from a known state. The transformation is a function of the last k information symbols, where k is the constraint length of the code and determines the length of a shift register. While FEC codes tend to require greater bandwidth than other error-correcting codes, FEC codes are more appropriate for correcting errors “on the fly” as data comes in.
In a system using trellis decoding, the results generated after a computational latency in a forward direction are then read in a reverse order in order to find the maximal likelihood path through the trellis. The decoding process consists of a branch metric block which provides cost information for the data coming into the decoder, a path metric unit such as an add-compare-select (ACS) block which compares the costs on the branches of the trellis, and a traceback block which traces back through the paths generated from the path metric unit to find the optimum path through the trellis to enable decoding of the data. Prior to the traceback process, the data has been processed by the branch metric unit and the path metric unit so that the data being written to the BRAM is the optimal path for each state in the trellis.
In the example of a trellis diagram of FIG. 2, the various paths from a given state to a next state are shown for a time period t=0 through t=2, where the available paths between states are defined by the encoder. The solid lines show the optimal path, the dashed lines shown the other available paths based upon a starting point of state 00, while the dotted lines show the available paths from the other states. That is, although the starting point at t=0 is state 00, the paths could extend from any of the other states at later time periods. Each state has cost value at a given time (i.e., a path metric) and each path has a given cost to each next state (i.e., a branch metric). The cost of a given path will be based upon the sum of the old path metric and the branch metric. There are always multiple paths for each state in the trellis. In the example of FIG. 2, the trellis is implanted using Radix-2. However, a trellis having more states may also be implemented. For example, a trellis could be implemented using Radix-4 having 4 paths to each state.
While there are many metrics which may be used to determine a cost from one state to another, one metric which may be used is based upon the number of bits which are different between the encoder output data and the data which is expected to be output when moving to the next state. The paths to the next state and outputs associated with the given paths are shown in the state diagram for all of the paths, where the first number before the slash mark represents the input to the encoder and the number after the slash mark represents the output of the encoder. For example, changing the bits of an output having a value 00 to a value 01 would require one bit to change, while changing the bits of an output having a value 00 to value 11 would require two bits to change. If the state of the decoder at time t=0 is 00, there are two paths from state 00 at t=0 either to state 00 or to state 10 at t=1. That is, the path to state 00 is followed if a zero has been encoded, while the path to state 10 is followed if a 1 has been encoded. At time t=1, the allowed paths from state 00 are either to state 00 if a 0 is encoded or to state 10 if a 1 has been encoded. If a 0 has been encoded and the current state is state 00, then the encoder will transmit 00 and the two input bits 00 will be received by the decoder provided the data has not been corrupted in the transmission. Similarly, if a 1 has been encoded and the current state is state 00, then the encoder will transmit 11 and 11 will be received by the decoder provided the data has not been corrupted in the transmission. To generate the branch metrics, the input data from the channel is compared with the expected input data should the trellis have taken the given path. Thus, in FIG. 2, if the current state is state 00 and we receive the input data 00, the cost of path 0. (using the simple Hamming distance metric) would be 0 as the expected data for the path is 00. The cost of path 1 is 2 because the expected data for this path is 11 which differ in both bits from the incoming data 00. While the Hamming distance is described to merely explain generating a cost for a path, a Euclidean distance metric is more commonly used.
A path selection for the various paths is selected according to the sum of a cost associated with a given state at a given time and a cost for taking a given path to the next state. A path selection cost associated with each state at a time t=2 is shown next to the state. For example, there is no cost for the path from state 00 at t=0 to state 00 at t=1. That is, the digits of the output 00 are the same as the expected output when moving from state 00 to state 00, and therefore no digits are different. Similarly, there is no cost for the path from state 00 at t=1 to state 10 at t=2. That is, there are no different bits in the encoder output which is 11 compared to the path output. Accordingly, the path shown in solid lines is the least cost path.
There are also costs which are greater than the least cost path for both available branches shown in dashed lines. In particular, the cost of the path from state 00 to state 00 at time t=2 is 2 because both bits of 00 expected to be received at state 00 are different from the output 11 of the encoder. Similarly, the cost of the path from state 10 to state 01 at time t=2 is 1 because one bit of the output 11 is different from the expected output 10. Accordingly, the total cost of the path is equal to 3. Finally, the cost of the available path from state 01 to state 11 is also equal to 2, while the total cost of the path is equal to 3. The chosen path from the ACS unit is saved in the traceback block for each state. That is, either a 1 or a 0 stored to select the path between states at each time period. In a standard Viterbi decoder having a constraint length of 7, there are 64 bits which are written to the traceback memory on each clock cycle to represent the paths between states. The traceback length is the number of time steps required to be traced back to find the correct path.
When a circuit having a given function is implemented in an integrated circuit, it is important to provide the most efficient use of circuit resources. Conventional circuits implementing a trellis decoder provide an inefficient use of resources of the integrated circuit. The efficient use of resources of an integrated circuit may be particularly significant in cases when resources are scarce. For example, the efficient use of logic resources and memory elements in a programmable logic device will enable more circuits to be implemented on a single programmable logic device. As will be described in more detail below, the requirement for additional memory blocks to implement the trellis decoder of a conventional device is inefficient, and particularly inefficient in a programmable logic device where the use of memory resources needs to be optimized.
Accordingly, there is a need for an improved method of and circuit for accessing a memory of a trellis decoder.